package xyz.scootaloo.oj.leetcode;

import xyz.scootaloo.console.app.support.Tester;

import java.util.ArrayDeque;

/**
 * 哨兵
 * 单调栈
 * @author flutterdash@qq.com
 * @since 2021/3/22 20:06
 */
public class P85 {

    public int maximalRectangle(char[][] matrix) {
        int row = matrix.length;
        if (row == 0)
            return 0;
        int column = matrix[0].length;
        if (column == 0)
            return 0;

        int[][] dp = new int[row][column];
        // 初始化第一行
        for (int c = 0; c<column; c++)
            dp[0][c] = matrix[0][c] == '1' ? 1 : 0;
        // 初始化第一列
        for (int r = 1; r<row; r++)
            dp[r][0] = matrix[r][0] == '1' ? dp[r - 1][0] + 1 : 0;

        // 初始化其余区域
        for (int r = 1; r<row; r++) {
            for (int c = 1; c<column; c++) {
                if (matrix[r][c] == '1') {
                    dp[r][c] = dp[r - 1][c] + 1;
                }
            }
        }

        int maxArea = 0;
        int[] tmp = new int[column + 2];
        ArrayDeque<Integer> stack = new ArrayDeque<>(tmp.length);
        for (int[] ROW : dp) {
            maxArea = Math.max(maxArea, getMaxArea(ROW, tmp, stack));
        }
        return maxArea;
    }

    private int getMaxArea(int[] row, int[] tmp, ArrayDeque<Integer> stack) {
        prepareData(row, tmp, stack);
        int maxArea = 0;
        for (int pos = 0; pos<tmp.length; pos++) {
            int currentArea = tmp[pos];
            while (currentArea < tmp[stack.peekLast()]) {
                int currentHeight = tmp[stack.pollLast()];
                int currentWidth = pos - stack.peekLast() - 1;
                maxArea = Math.max(maxArea, currentWidth * currentHeight);
            }
            stack.addLast(pos);
        }
        return maxArea;
    }

    private void prepareData(int[] row, int[] tmp, ArrayDeque<Integer> stack) {
        System.arraycopy(row, 0, tmp, 1, row.length);
        stack.clear();
        stack.addLast(0);
    }

    public static void main(String[] args) {
        char[][] board_1 = {
                {'1', '0', '1', '0', '0'},
                {'1', '0', '1', '1', '1'},
                {'1', '1', '1', '1', '1'},
                {'1', '0', '0', '1', '0'}
        };
        char[][] board_2 = {
                {'1', '0', '1', '0', '0'},
                {'1', '0', '1', '1', '1'},
                {'1', '1', '1', '0', '1'},
                {'1', '0', '0', '1', '0'}
        };
        Tester.createTest(new P85()::maximalRectangle)
                .addCase(board_1, 6)
                .addCase(board_2, 4)
                .test();
    }

}
